// [2071]${question.tilte}
struct Solution;

//leetcode submit region begin(Prohibit modification and deletion)
impl Solution {
    pub fn max_task_assign(tasks: Vec<i32>, workers: Vec<i32>, pills: i32, strength: i32) -> i32 {
        let mut tasks = tasks;
        let mut workers = workers;
        let mut worker_len = workers.len();
        tasks.sort();
        workers.sort();
        let check = |worker_num| {
            let mut valid_tasks = std::collections::VecDeque::new();
            let mut pills = pills;
            let mut task_index = 0;
            for &worker in &workers[(worker_len - worker_num)..worker_len] {
                while task_index < worker_num && tasks[task_index] <= worker + strength {
                    valid_tasks.push_back(tasks[task_index]);
                    task_index += 1;
                }
                // 吃药也完不成任务
                if valid_tasks.is_empty() {
                    return false;
                }

                // 不吃药也能完成最简单的任务
                if worker >= *valid_tasks.front().unwrap() {
                    // 优先完成简单任务
                    valid_tasks.pop_front();
                    continue;
                }
                // 需要吃药，但没药了
                if pills <= 0 {
                    return false;
                }

                // 吃药完成最难的任务
                pills -= 1;
                valid_tasks.pop_back();
            }
            true
        };

        // 左闭右开，left肯定是有效的
        let mut left = 0;
        let mut right = tasks.len().min(worker_len) + 1;
        while left + 1 < right {
            let mid = left + (right - left) / 2;
            if check(mid) {
                left = mid;
            } else {
                right = mid;
            }
        }
        left as _
    }
}
//leetcode submit region end(Prohibit modification and deletion)

/// 总结：
/// 1. 假定答案
/// 2. 配对

#[test]
fn main() {
    let tasks = vec![3, 2, 1];
    let workers = vec![0, 3, 3];
    let pills = 1;
    let strength = 1;
    assert_eq!(
        Solution::max_task_assign(tasks, workers, pills, strength),
        3
    );

    let tasks = vec![5, 4];
    let workers = vec![0, 0, 0];
    let pills = 1;
    let strength = 5;
    assert_eq!(
        Solution::max_task_assign(tasks, workers, pills, strength),
        1
    );

    let tasks = vec![10, 15, 30];
    let workers = vec![0, 10, 10, 10, 10];
    let pills = 3;
    let strength = 10;
    assert_eq!(
        Solution::max_task_assign(tasks, workers, pills, strength),
        2
    );

    let tasks = vec![5, 9, 8, 5, 9];
    let workers = vec![1, 6, 4, 2, 6];
    let pills = 1;
    let strength = 5;
    assert_eq!(
        Solution::max_task_assign(tasks, workers, pills, strength),
        3
    );
    let tasks = vec![35];
    let workers = vec![83, 20, 4, 66];
    let pills = 3;
    let strength = 41;
    assert_eq!(
        Solution::max_task_assign(tasks, workers, pills, strength),
        1
    );
}
